//headers 
#include<algorithm>
#include<cassert>
#include<cstdio>
#include<queue>
#include<deque>
#include<iostream>
#include<list>
#include<map>
#include<numeric>
#include<deque>
#include<set>
#include<string>
#include<sstream>
#include<stack>
#include<streambuf>
#include<vector>
using namespace std;

//macros
#define LET(x,a) typeof(a) x(a)
#define FOR(i,a,n) for(LET(i,a);i!=n;i++)
#define REP(i,n) FOR(i,0,n)
#define sz size()
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define PRINT(x) REP(_,x.sz) cout<<x[_]<<" "; cout<<endl;
const int INF = (int) 1e8;
#define VI vector<int>
#define VS vector<string>
#define VVI vector< vector<int> >
#define PII pair<int,int>
#define VII vector< PII >
#define LL long long
#define mp make_pair


//code of suren
int dp[10001];
int visited[10001];

LL go( string s , int pos , vector< pair<string,int> > &dic , int &p){
  if(visited[pos]) return dp[pos];
  if(s.sz==0) return 0;
  
  LL ret = -INF;

  REP(i,dic.sz) {
    LL temp;
    int len = dic[i].first.sz; 
    if( dic[i].first == string(s,0,len) )  {
      string new_s = string(s,len);
      temp = -p + go(string(s,1),pos+1,dic,p);
      LL temp2 = dic[i].second + go(new_s, pos+len , dic , p); 
      temp = max(temp,temp2);
    }
    else temp = -p + go(string(s,1),pos+1,dic,p);
    ret = max(ret,temp);          
  }
    
  dp[pos]=ret;
  visited[pos]=1;
  return ret;
}


int main(){
  int t; cin>>t;
  REP(k,t){
    int n , p; vector< pair<string,int> > dic;
    cin>>n>>p;
    REP(i,n){ string temp; int val; cin>>temp>>val; dic.pb(mp(temp,val)); }
    memset(dp,0,sizeof(dp));
    memset(visited,0,sizeof(visited));
    string final; cin>>final;
    LL ans = -INF;
    ans = max( ans , go( final , 0 , dic , p) );
    cout<<"Case "<<k+1<<": "<<ans<<endl;
  }
  return 0;
}
